package fun.coding.zulily;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class SumToTarget {

	public enum MethodType {
        SORT,
        HASH
    }
	
	public static HashSet<ArrayList<Integer>> sumToTarget(int[] array, int target, MethodType type) throws Exception {
		if(array == null || array.length < 2)
			throw new Exception("Invalid input!");
		
		HashSet<ArrayList<Integer>> res = new HashSet<ArrayList<Integer>>();
        
        if(type == MethodType.SORT) {
            Arrays.sort(array);
            
            int i = 0;
            int j = array.length - 1;
            
            while(i < j) {
                if(array[i] + array[j] < target) {
                    i++;
                } else if(array[i] + array[j] > target) {
                    j--;
                } else {
                    ArrayList<Integer> al = new ArrayList<Integer>();
                    // Uniqueness is already maintained since array is sorted.
                    al.add(array[i]);
                    al.add(array[j]);
                    res.add(al);
                    i++;
                    j--;
                }
            }
        } else if(type == MethodType.HASH) {
            HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
            
            for(int i : array) {
            	int j = target - i;
            	if(hashMap.containsKey(j)) {
            		ArrayList<Integer> al = new ArrayList<Integer>();
            		// Maintain the uniqueness by sorting these 2 numbers.
            		al.add(Math.min(i, j));
            		al.add(Math.max(i, j));
            		res.add(al);
            		if((hashMap.get(j) - 1) == 0) {
            			 hashMap.remove(j);
            		} else {
            			hashMap.put(j, hashMap.get(j) - 1);
            		}
            	} else {
            		hashMap.put(i, hashMap.containsKey(i) ? hashMap.get(i) + 1 : 1);
            	}
            }
        }
        
        return res;
	}
	
	public static ArrayList<int[]> initTestCases() {
		ArrayList<int[]> testCases = new ArrayList<int[]>();
		
		int[] t1 = {-1, 1, -1, 1, 0, 0};
		int[] t2 = {-1, 1, -1, 1, 0};
		int[] t3 = {0, 0, 0};
		int[] t4 = {1, 1, 1};
		int[] t5 = null;
		int[] t6 = {1};
		
		testCases.add(t1);
		testCases.add(t2);
		testCases.add(t3);
		testCases.add(t4);
		testCases.add(t5);
		testCases.add(t6);
		
		return testCases;
	}
	
	public static void runTestsSuite(ArrayList<int[]> testCases, int target, MethodType type) {
		System.out.println("Running " + type.toString());
		for(int[] array : testCases) {
			try {
				HashSet<ArrayList<Integer>> res = sumToTarget(array, target, type);
				
				System.out.println(res);
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
	}
	
	public static void main(String[] args) {
		ArrayList<int[]> testCases = initTestCases();
		runTestsSuite(testCases, 0, MethodType.SORT);
		runTestsSuite(testCases, 0, MethodType.HASH);
	}
	
}
